package two.tree;

/**
 * 二叉树的最大深度:
 */
public class MaxDepth {
    /**
     时间复杂度：O(n)
     思路：自底向上递归
     */
    // public int maxDepth(TreeNode root) {
    //     if(root == null) return 0; //边界
    //     return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; //本层处理+子问题
    // }
    /**
     时间复杂度：O(n)
     思路：自顶向下递归
     */
    public int maxDepth(TreeNode root) {
        ans = 0;
        calc(root, 1);
        return ans;
    }
    private void calc(TreeNode root, int depth){
        if(root == null) return; //边界
        ans = Math.max(ans, depth); //本层处理
        calc(root.left, depth + 1); //子问题
        calc(root.right, depth + 1);
    }

    private int ans;//结果
}
